package com.maisuiit.basics;

import java.util.Calendar;

//演示4种排序法
public class Sort {
    public static void main(String[] args) {
        int len=100000;
        int arr1[]=new int[len];
        for(int i=0;i<len;i++){
            //让程序随机产生1-10000数
            //Math.random()会随机产生一个0-1的数
            int t=(int)(Math.random()*10000);
            arr1[i]=t;
        }

        //创建一个Bubble冒泡类
        Bubble bubble=new Bubble();
        //计算排序系统时间
        Calendar cal=Calendar.getInstance();
        System.out.println("Bubble冒泡排序开始时间："+cal.getTime());
        bubble.sort(arr1);
        //重新得到实例
        cal=Calendar.getInstance();
        System.out.println("Bubble冒泡排序结束时间："+cal.getTime());

        //创建一个select选择类
        Select select=new Select();
        //计算排序系统时间
        Calendar cal1=Calendar.getInstance();
        System.out.println("Select选择排序开始时间："+cal1.getTime());
        select.sort(arr1);
        //重新得到实例
        cal1=Calendar.getInstance();
        System.out.println("Select选择排序结束时间："+cal1.getTime());

        //创建一个InsertSort插入类
        InsertSort is=new InsertSort();
        //计算排序系统时间
        Calendar cal2=Calendar.getInstance();
        System.out.println("InsertSort插入排序开始时间："+cal2.getTime());
        is.sort(arr1);
        //重新得到实例
        cal2=Calendar.getInstance();
        System.out.println("InsertSort插入排序结束时间："+cal2.getTime());

        //创建一个QuickSort快速类
        QuickSort qs=new QuickSort();
        //计算排序系统时间
        Calendar cal3=Calendar.getInstance();
        System.out.println("QuickSort快速排序开始时间："+cal3.getTime());
        qs.sort(0,arr1.length-1,arr1);
        //重新得到实例
        cal3=Calendar.getInstance();
        System.out.println("QuickSort快速排序结束时间："+cal3.getTime());
        //输出最后结果
        //	for(int i=0;i<arr1.length;i++){
        //		System.out.print(arr1[i]+"\t");
        //	}


    }

}

//快速排序法
class QuickSort{
    public void sort(int left,int right,int [] arr){
        int l=left;
        int r=right;
        int pivot=arr[(left+right)/2];
        int temp=0;
        while(l<r){

            while(arr[l]<pivot) l++;
            while(arr[r]>pivot) r--;

            if(l>=r) break;

            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;

            if(arr[l]==pivot) --r;
            if(arr[r]==pivot) ++l;
        }
        if(l==r){
            l++;
            r--;
        }
        if(left<r) sort(left,r,arr);
        if(right>l) sort(l,right,arr);
    }
}

//插入式排序法
class InsertSort{
    //插入排序方法
    public void sort(int arr[]){
        for(int i=1;i<arr.length;i++){
            int insertVal=arr[i];
            //insertVal准备和前一个数比较
            int index=i-1;
            while(index>=0&&insertVal<arr[index]){
                //将把arr[index]向后移动一位
                arr[index+1]=arr[index];
                //让index向前移动一位
                index--;
            }
            //将insertVal插入到适当位置
            arr[index+1]=insertVal;
        }
    }
}


class Select{//选择排序法
    //选择排序
    public void sort(int arr[]){
        int temp=0;
        for(int j=0;j<arr.length-1;j++){
            //认为第一个数就是最小数
            int min=arr[j];
            //记录最小数的下标
            int minIndex=j;

            for(int k=j+1;k<arr.length;k++){
                if(min>arr[k]){
                    //修改最小值
                    min=arr[k];
                    minIndex=k;
                }
            }
            //当退出for循环时就找到这次的最小值
            temp=arr[j];
            arr[j]=arr[minIndex];
            arr[minIndex]=temp;
        }
    }

}

class Bubble{//冒泡排序
    //排序方法
    public void sort(int arr[]){
        int temp=0;
        //排序
        //外层循环，可以决定一共走趟
        for(int i=0;i<arr.length-1;i++){
            //内层循环，开始逐个比较，如果发现前一个数比后一个数大则交换
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    //换位
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }

    }

}
